package gold.digger;


import gold.vo.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC107 {



    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<TreeNode> curLevelNode = new LinkedList<>();
            List<Integer> curLevelVal = new LinkedList<>();
            while (!queue.isEmpty()) {
                curLevelNode.add(queue.poll());
            }
            for (TreeNode node : curLevelNode) {
                curLevelVal.add(node.val);
                if (null != node.left) {
                    queue.offer(node.left);
                }
                if (null != node.right) {
                    queue.offer(node.right);
                }
            }
            res.add(curLevelVal);
        }

        Collections.reverse(res);
        return res;
    }


    public void run01() {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(2);
        TreeNode d = new TreeNode(2);
        TreeNode e = new TreeNode(2);
        TreeNode f = new TreeNode(4);
        TreeNode g = new TreeNode(3);

        a.left = b;
        a.right = c;

        b.left = d;
//        b.right = e;

        c.left = e;
//        c.right = g;
        System.out.println(levelOrderBottom(null));
    }

//    public void run02() {
//        TreeNode a = new TreeNode(1);
//        TreeNode b = new TreeNode(2);
//        TreeNode c = new TreeNode(2);
//        TreeNode d = new TreeNode(2);
//        TreeNode e = new TreeNode(2);
//        TreeNode f = new TreeNode(4);
//        TreeNode g = new TreeNode(3);
//
//        a.right = b;
//
//        System.out.println(isSymmetric(a));
//    }

    public static void main(String[] args) {
        LC107 an = new LC107();
        an.run01();
    }
}
